
/**
 * @Project : Clion_ProgrammingExercises
 * @File : 0005
 * @Author : WangRuoyu 
 * @Date : 2023/5/24 16:57
 */

#include "iostream"

using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int f[s.size()][s.size()];
        for (int i = 0; i < s.size(); ++i) {
            for (int j = 0; j < s.size(); ++j) {
                if (i == j) f[i][j] = 1;
                else f[i][j] = 0;
            }
        }

        int l = 0, r = 0, curlen = 1;
        for (int len = 2; len <= s.size(); ++len) {
            for (int i = 0; i <= s.size() - len; ++i) {
                int j = i + len - 1;
                if (s[i] == s[j] && f[i + 1][j - 1] != -1) {
                    f[i][j] = f[i + 1][j - 1] + 2;
                    if (f[i][j] > curlen) {
                        l = i;
                        r = j;
                        curlen = f[i][j];
                    }
                } else {
                    f[i][j] = -1;
                }
            }
        }
        return s.substr(l, r + 1 - l);
    }
};

int main() {
    Solution sl;
    string str = "babad";
    cout << sl.longestPalindrome(str);
    return 0;
}